DROPS

Document

DOI: 10.4230/LIPIcs.STACS.2023.31

Barriers for Faster Dimensionality Reduction

Authors: Ora Nova Fandina, Mikael Møller Høgsgaard, and Kasper Green Larsen

Published in: LIPIcs, Volume 254, 40th International Symposium on Theoretical Aspects of Computer Science (STACS 2023)

Abstract

The Johnson-Lindenstrauss transform allows one to embed a dataset of n points in ℝ^d into ℝ^m, while preserving the pairwise distance between any pair of points up to a factor (1 ± ε), provided that m = Ω(ε^{-2} lg n). The transform has found an overwhelming number of algorithmic applications, allowing to speed up algorithms and reducing memory consumption at the price of a small loss in accuracy. A central line of research on such transforms, focus on developing fast embedding algorithms, with the classic example being the Fast JL transform by Ailon and Chazelle. All known such algorithms have an embedding time of Ω(d lg d), but no lower bounds rule out a clean O(d) embedding time. In this work, we establish the first non-trivial lower bounds (of magnitude Ω(m lg m)) for a large class of embedding algorithms, including in particular most known upper bounds.

Cite as

Ora Nova Fandina, Mikael Møller Høgsgaard, and Kasper Green Larsen. Barriers for Faster Dimensionality Reduction. In 40th International Symposium on Theoretical Aspects of Computer Science (STACS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 254, pp. 31:1-31:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{novafandina_et_al:LIPIcs.STACS.2023.31,
  author =	{Nova Fandina, Ora and M{\o}ller H{\o}gsgaard, Mikael and Green Larsen, Kasper},
  title =	{{Barriers for Faster Dimensionality Reduction}},
  booktitle =	{40th International Symposium on Theoretical Aspects of Computer Science (STACS 2023)},
  pages =	{31:1--31:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-266-2},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{254},
  editor =	{Berenbrink, Petra and Bouyer, Patricia and Dawar, Anuj and Kant\'{e}, Mamadou Moustapha},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2023.31},
  URN =		{urn:nbn:de:0030-drops-176838},
  doi =		{10.4230/LIPIcs.STACS.2023.31},
  annote =	{Keywords: Dimensional reduction, Lower bound, Linear Circuits}
}

Search Results

Documents authored by Green Larsen, Kasper

Barriers for Faster Dimensionality Reduction

Abstract

Cite as

Thanks for your feedback!

Could not send message